package leetcode.problems;

import java.util.ArrayList;
import java.util.List;

/**
 * Find All Anagrams in a String
 * 查找字符串中的所有字母组合
 * Created by gmwang on 2018/3/23
 */
public class _0324FindAllAnagramsinaString {
    /**
     * Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.
     * <p>
     * Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.
     * <p>
     * The order of output does not matter.
     * <p>
     * Example 1:
     * <p>
     * Input:
     * s: "cbaebabacd" p: "abc"
     * <p>
     * Output:
     * [0, 6]
     * <p>
     * Explanation:
     * The substring with start index = 0 is "cba", which is an anagram of "abc".
     * The substring with start index = 6 is "bac", which is an anagram of "abc".
     * Example 2:
     * <p>
     * Input:
     * s: "abab" p: "ab"
     * <p>
     * Output:
     * [0, 1, 2]
     * <p>
     * Explanation:
     * The substring with start index = 0 is "ab", which is an anagram of "ab".
     * The substring with start index = 1 is "ba", which is an anagram of "ab".
     * The substring with start index = 2 is "ab", which is an anagram of "ab".
     * <p>
     * 给定一个字符串小号和非空字符串p，找到的所有开始指数p中的字谜小号。
     * 字符串只包含小写英文字母，字符串s和p的长度不会超过20,100。
     * 输出的顺序并不重要。
     * <p>
     * 例1：
     * <p>
     * 输入：
     * s：“cbaebabacd”p：“abc” 输出：
     * [ 0，6 ] 说明：
     * 起始索引= 0的子字符串是“cba”，它是“abc”的一个字母组合。
     * 起始索引= 6的子字符串是“bac”，它是“abc”的一个字母。
     * <p>
     * 例2：
     * <p>
     * 输入：
     * s：“abab”p：“ab” 输出：
     * [0，1，2] 说明：
     * 起始索引= 0的子字符串是ab，它是ab的一个字母。
     * 开始索引= 1的子字符串是“ba”，它是“ab”的一个字母组合。
     * 起始索引= 2的子字符串是“ab”，它是“ab”的一个字母组合。
     */
    public static List<Integer> findAnagrams(String s, String p) {
        //cbaebabacd
        ArrayList<Integer> list = new ArrayList<>();
        char[] array = s.toCharArray();
        for (int sir = 0; sir < array.length - p.length() + 1; sir++) {
            String sirs = s.substring(sir, sir + p.length());
            char[] arraySirs = sirs.toCharArray();
            char[] arrayP = p.toCharArray();
            int sirRes = 0, pRes = 0;
            for (int l = 0; l < (arraySirs.length>arrayP.length?arraySirs.length:arrayP.length); l++) {
                sirRes += arraySirs[l] - 'a';
                pRes += arrayP[l] - 'a';
            }
            if (sirRes == pRes) list.add(sir);
        }
        return list;
    }

    public static void main(String[] args) {
        long first = System.nanoTime();
        System.out.println(first);
        String s = "cbaebabacd";
        String p = "abc";
        System.out.println(findAnagrams(s, p));
        System.out.println(System.nanoTime() - first);
    }
}
